package Test;

import java.util.Arrays;

/*
动态规划
 */
public class 零钱兑换 {
    int[] memo;

    public int coinChange(int[] coins, int amount) {
        memo=new int[amount+1];

        Arrays.fill(memo,-6);
        return dp(coins,amount);
    }
    int dp(int[] coins,int amount){
        if(amount==0) return 0;
        if(amount<0) return -1;
        if(memo[amount]!=-6) return memo[amount];
        int res=Integer.MAX_VALUE;
        for (int i=0;i<coins.length;i++){
            int result=dp(coins,amount-coins[i]);
            if(result==-1) continue;
            res=Math.min(res,result+1);
        }
        memo[amount]=res==Integer.MAX_VALUE?-1:res;
        return memo[amount];
    }

}
